# @before-stub-for-debug-begin
from python3problem654 import *
from typing import *
# @before-stub-for-debug-end

#
# @lc app=leetcode.cn id=654 lang=python3
#
# [654] 最大二叉树
#
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
from typing import List
# @lc code=start
# Definition for a binary tree node.
class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:
        if len(nums) == 0:
            return None
        return self.construct(nums, 0, len(nums))
        
    def construct(self, nums: List[int], start: int, end: int) -> TreeNode:
        if start == end:
            return None
        idx = 0
        val = -1
        for i in range(start, end):
            if nums[i] > val:
                val = nums[i]
                idx = i

        root = TreeNode(val)
        root.left = self.construct(nums, start, idx)
        root.right = self.construct(nums, idx+1, end)
        return root
# @lc code=end

